package leetcode_top;
import java.util.*;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.LockSupport;
import java.util.concurrent.locks.ReentrantLock;

import org.junit.Test;
public class Ex380 {
    class RandomizedSet1 {
        private Map<Integer, Integer> map;
        private Map<Integer, Integer> idx;
        List<Integer> rm;
        private int count;

        public RandomizedSet1() {
            count = 0;
            rm = new LinkedList<>();
            map = new HashMap<>();
            idx = new HashMap<>();
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if (!map.containsKey(val)) {
                map.put(val, count);
                idx.put(count++, val);
                return true;
            }
            return false;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if (!map.containsKey(val)) return false;
            else {
                int i = map.get(val);
                map.remove(val);
                count--;
                if (count != 0) {
                    int last = idx.get(count);
                    map.remove(last);
                    idx.remove(count);
                    map.put(last, i);
                    idx.put(i, last);
                }
                return true;
            }
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            return idx.get((int)(Math.random() * count));
        }
    }
    
    class RandomizedSet {
        private Map<Integer, Integer> map;
        List<Integer> idx;
        private int count;

        public RandomizedSet() {
            count = 0;
            map = new HashMap<>();
            idx = new ArrayList<>();
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if (!map.containsKey(val)) {
                map.put(val, count++);
                idx.add(val);
                return true;
            }
            return false;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if (!map.containsKey(val)) return false;
            else {
                count--;
                int tmp = idx.remove(count);
                int i = map.remove(val);
                if (count != 0) {
                    map.put(tmp, i);
                    idx.set(i, tmp);
                }
                return true;
            }
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            return idx.get((int)(Math.random() * idx.size()));
        }
    }

    @Test
    public void test() {
        LockSupport.park();
        Condition condition = new ReentrantLock().newCondition();
        try {
            condition.await();
        } catch (Exception e) {
        }
    }

}
